UVA10859 Placing Lampposts

nn 个点 mm 条边的无向无环图,其实就是一个森林。

题目要求最小化两个量:灯数和只被一边照亮的边数。

一个做法是定义两个 dpdp 数组,分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。

然后你发现它们是一起转移的,那么就有一个极妙的做法:

将它们的贡献算在一起,因为灯数的优先级高,所以给它乘上一个权值 kk。(这里 kk 可以取任意不小于 nn 的值 ,可以理解为 kk 进制的高低位),那么加一个灯贡献加 kk ,加一条单灯边贡献加 11

那么转移就变为:

{dp[u][0]=vsonudp[v][1]+1dp[u][1]=k+vsonumin{dp[v][0]+1,dp[v][1]}\begin{cases} dp[u][0]=\sum_{v \in son_u} dp[v][1]+1 \\ dp[u][1]=k+\sum_{v \in son_u} \min\{ dp[v][0]+1,dp[v][1] \} \end{cases}

最后只需要除以 kk ,和膜 kk 便能得到分别的答案。

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1000 , k = 1005;
int T , n , m;
vector< int > Graph[ MAXN + 5 ];

int dp[ 2 ][ MAXN + 5 ];
void dfs( int u , int fa ) {
    dp[ 0 ][ u ] = 0 , dp[ 1 ][ u ] = k;
    for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( v == fa ) continue;
        dfs( v , u );
        dp[ 0 ][ u ] += dp[ 1 ][ v ] + 1;
        dp[ 1 ][ u ] += min( dp[ 0 ][ v ] + 1 , dp[ 1 ][ v ] );
    }
}

int main( ) {
    scanf("%d",&T);
    while( T -- ) {
        scanf("%d %d",&n,&m);
        for( int i = 1 ; i <= n ; i ++ ) Graph[ i ].clear() , dp[ 0 ][ i ] = 0 , dp[ 1 ][ i ] = 0;
        for( int i = 1 , u , v ; i <= m ; i ++ ) {
            scanf("%d %d",&u,&v); u ++ , v ++;
            Graph[ u ].push_back( v );
            Graph[ v ].push_back( u );
        }

        int Ans1 = 0 , Ans2 = 0;
        for( int i = 1 ; i <= n ; i ++ )
            if( !dp[ 1 ][ i ] ) {
                dfs( i , 0 );
                Ans1 += min( dp[ 0 ][ i ] , dp[ 1 ][ i ] ) / k;
                Ans2 += min( dp[ 0 ][ i ] , dp[ 1 ][ i ] ) % k;
            }
        printf("%d %d %d\n", Ans1 , m - Ans2 , Ans2 );
    }
    return 0;
}